package com.yww.leetcode.binarysearch;

/**
 * @author yww
 * @description 35. 搜索插入位置
 * @since 2024/1/29 15:05
 */
public class SearchInsert35 {
    // 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
    // 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
    public int searchInsert(int[] nums, int target) {
        if (nums.length % 2 == 0) {
            return searchInsertPoint(nums, target);
        } else {
            return searchLeftmost(nums, target);
        }

    }

    // 返回 -(InsertPoint + 1) ---- > InsertPoint
    public static int searchInsertPoint(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < nums[m]) {
                j = m - 1;
            } else if (nums[m] < target) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return i;
    }

    // leftmost 返回最左侧 >= target 的索引
    public static int searchLeftmost(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < nums[m]) {
                j = m - 1;
            } else if (nums[m] < target) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        return i;
    }
}
